#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>

int g(vector<int>& arr , int L , int R);
int f(vector<int>& arr , int L , int R);


int f(vector<int>& arr , int L , int R)
{
  if (L == R)
  {
    return arr[L];
  }

  int p1 = arr[L] + g(arr , L + 1 , R );
  int p2 = arr[R] + g(arr , L , R - 1);

  return max(p1 , p2);
}


int g(vector<int>& arr , int L , int R)
{
  if (L == R)
  {
    return 0;
  }

  int p1 = f(arr , L + 1 , R);
  int p2 = f(arr , L , R -1);

  return min(p1 , p2);
}


int g2(vector<int>& arr , int L , int R);
int f2(vector<int>& arr , int L , int R);


int _g2(vector<int>& arr , int L , int R , vector<vector<int>>& fmap , vector<vector<int>>& gmap);
int _f2(vector<int>& arr , int L , int R , vector<vector<int>>& fmap , vector<vector<int>>& gmap);





int f2(vector<int>& arr , int L , int R)
{

  vector<vector<int>> fmap( R+1 , vector<int>(R+1));
  for (int i = 0 ; i < R + 1 ; i++)
  {
    for (int j = 0; j < R + 1 ; j++)
    {
      fmap[i][j] = 0;
    }
  }

  vector<vector<int>> gmap( R+1 , vector<int>(R+1));
  for (int i = 0 ; i < R + 1 ; i++)
  {
    for (int j = 0; j < R + 1 ; j++)
    {
      gmap[i][j] = 0;
    }
  }
  return _f2(arr , L , R , fmap , gmap);
}


int g2(vector<int>& arr , int L , int R)
{
  vector<vector<int>> fmap( R+1 , vector<int>(R+1));
  for (int i = 0 ; i < R + 1 ; i++)
  {
    for (int j = 0; j < R + 1 ; j++)
    {
      fmap[i][j] = 0;
    }
  }

  vector<vector<int>> gmap( R+1 , vector<int>(R+1));
  for (int i = 0 ; i < R + 1 ; i++)
  {
    for (int j = 0; j < R + 1 ; j++)
    {
      gmap[i][j] = 0;
    }
  }

  return _g2(arr , L , R , fmap , gmap);
}

 
int _g2(vector<int>& arr , int L , int R , vector<vector<int>>& fmap , vector<vector<int>>& gmap)
{
  if (gmap[L][R] != 0)
  {
    return gmap[L][R];
  }

  int ans = 0;

  if (L == R)
  {
    ans = 0;
  }
  else 
  {
    int p1 = _f2(arr , L , R -1 , fmap , gmap);
    int p2 = _f2(arr , L + 1 , R , fmap , gmap);
    ans = min(p1 , p2);
  }

  gmap[L][R] = ans; 
  return ans;
}



int _f2(vector<int>& arr , int L , int R , vector<vector<int>>& fmap , vector<vector<int>>& gmap)
{
  if (fmap[L][R] != 0)
  {
    return fmap[L][R];
  }

  int ans = 0;

  if ( L == R)
  {
    ans = arr[L];
  }
  else 
  {
    int p1 = arr[L] + _g2(arr , L+1 , R , fmap , gmap);
    int p2 = arr[R] + _g2(arr , L , R-1 , fmap , gmap);
    ans = max(p1 , p2);
  }

  fmap[L][R] = ans;
  return ans;

}

int f3(vector<int>& arr , int L , int R)
{
  
  vector<vector<int>> fmap( R + 1, vector<int>(R+1));
  for (int i = 0 ; i < R + 1 ; i++)
  {
    for (int j = 0; j < R + 1 ; j++)
    {
      fmap[i][j] = 0;
      if (i == j)
      {
        fmap[i][j] = arr[i];
      }
    }
  }

  vector<vector<int>> gmap( R+1 , vector<int>(R+1));
  for (int i = 0 ; i < R + 1 ; i++)
  {
    for (int j = 0; j < R + 1 ; j++)
    {
      gmap[i][j] = 0;
    }
  }

  for (int startcol = 1 ; startcol < R + 1; startcol++ )
  {
     int col = startcol;
     int row = 0;

     while (col < R + 1)
     {
       fmap[row][col] = max(gmap[row][col-1] + arr[col] , gmap[row+1][col] + arr[row]);
       gmap[row][col] = min(fmap[row][col-1] , fmap[row+1][col]);

       row++;
       col++;
     }
  
  }

  return gmap[L][R];
}

int main()
{
  vector<int> arr = { 1 , 100 ,1 , 1 , 20 , 50 , 10};
  cout << f3(arr , 0 , 6) << endl;
  return 0;
}
